There is a continuing need for higher performance digital data communications systems. Perhaps nowhere is this need more evident than on the worldwide packet data communications network now commonly referred to as the “Internet.” On the Internet, the “richness” of content is constantly increasing, requiring an ever-increasing amount of bandwidth to provide Internet content to users. As a result of this increased demand for bandwidth, significant efforts have been made to develop new types of high-speed digital data communications systems. For example, optical fiber based networks are being built in many large metropolitan areas and undersea to connect continents. As another example, new wireless protocols are being developed to provide Internet content to many different types of small, portable devices.
One of the significant drawbacks of deploying many of these new types of high-speed digital data communications systems is the high cost and amount of time required to develop and build out the new infrastructure required by the systems. Because of these high costs, many new high-speed digital data communications systems are initially deployed only in densely populated areas, where the cost of building out the new infrastructure can be quickly recovered. Less populated areas must often wait to receive the new communications systems and some rural areas never receive the new systems where it is not cost effective to build the infrastructure.
For several reasons, significant efforts are being made to utilize conventional twisted pair telephone lines to provide high-speed digital data transmission. First, a significant amount of twisted pair telephone line infrastructure already exists in many countries. Thus, using conventional twisted pair telephone lines avoids the cost of building expensive new infrastructure. Second, conventional twisted pair telephone lines extend into customers' homes and businesses, avoiding the so-called “last mile” problem. As a result of recent development efforts in this area, several new communications protocols, such as ADSL, G.Lite and VDSL, have been developed for providing high-speed digital transmission over conventional twisted pair telephone lines.
Recent standards for digital subscriber line services such as ADSL and G.Lite use discrete multi-tone modulation (DMT) to implement multi-carrier communications systems. DMT is also under consideration for Very high speed Digital Subscriber Line (VDSL) services. By splitting the available bandwidth into a number of independently operating, narrow band tones, alternatively referred to as “channels” herein, such systems achieve high performance over channels with widely varying spectral characteristics. Each tone effectively operates as a (Quadrature Amplitude Modulation) QAM system. The DMT transmitter splits the input data stream into a number of sub-streams, and encodes each sub-stream into a sequence of points in a QAM constellation. The maximum number of bits that may be assigned to each tone is determined by the prevailing signal to noise ratio (SNR) on that tone.
In a QAM system with a constellation Cb consisting of 2b points at odd integer values (n, m), scaled by a factor d, and with additive Gaussian noise having power σ2, the symbol error probability is given by Pe=4Q(z) with z=√{square root over (2)}d/(γσ). The number γ is called the margin and the function Q is the tail area of the standard normal distribution:
      Q    ⁢          (      z      )        =            1                        2          ⁢          π                      ⁢                  ∫        z        ∞            ⁢                        ⅇ                                    -                              t                2                                      /            2                          ⁢                              ⅆ            t                    .                    
The margin operates as a guard when there is uncertainty about the operating conditions. If the system is required to operate at a symbol error probability Pe with a margin of γ2, then the error probability should be Pe when the noise power is a factor γ2 higher than its actual level. In addition, the constellation power is
  p  =                    2                  -          b                    ⁢              d        2            ⁢                        ∑                      C            b                          ⁢                  (                                    n              2                        +                          m              2                                )                      =                  2        3            ⁢              d        2            ⁢                        c          ⁢                      (            b            )                          .            The shape of the constellation determines the function c(b): typically c(b)=αb2b−1. For example, if b is even, c(b)=2b−1 for a square constellation with 2b points. Eliminating d yields
                              z          2                ⁢                  γ          2                    3        ⁢          c      ⁢              (        b        )              =            p              σ        2              =          SNR      .      This rearranges as
      c    ⁢          (      b      )        =            SNR      Γ        .  The quantity Γ=z2γ2/3 is called the SNR gap. In the presence of coding, the SNR gap (or equivalently, the margin) is reduced by the amount of the coding gain.
Given an operating margin and a desired symbol error probability, one determines a value for z and thus for Γ. For example, if Pe=10−7 and γ=6 dB then z=5.45 and Γ=6+9.96=15.96 dB in the absence of coding. Given a value for the SNR and the SNR gap, one obtains a value for the number of bits that may be transmitted on the tone by inverting c(b)=SNR/Γ and rounding b down to the nearest integer. This function may be conveniently implemented in a lookup table.
Determining b in this manner yields the maximum number of bits that can be transmitted on the tone without fine gain adjustment. If an additional gain g is applied at the transmitter, and the SNR is measured without taking account of the gain, then in linear scale
            g      2        ⁢          SNR      Γ        =            c      ⁢              (        b        )              .  Alternatively, in logarithmic scaleg+SNR−Γ=c(b).Given values for the number of bits b and the gain g, this equation determines the value of the SNR gap and thus the probability of a symbol error.
Conventional approaches attempt to minimize the variation in the probability of error across tones. This would be a trivial task if the gain on each tone could be arbitrarily chosen. However, system power constraints limit the aggregate gain across all channels, and communications standards sometimes impose further constraints on the individual gains. There may also be constraints on the number of bits. For example, there may be a minimum and a maximum value specified for the number of bits on each tone, and the total number of bits may be constrained to be a multiple of eight if information is transmitted in bytes. Also, a telecommunications provider may sell a service at a rate much less than the carrying capacity of the channel. In this case the total number of bits is specified in advance. Based on the foregoing, it is desirable to assign bits and gains to tones to maximize margins, while minimizing variations in margins between tones.